import org.omg.CORBA.PUBLIC_MEMBER;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class MyPriorityQueue{

    public int[] elem;
    public int usedSize;


    public MyPriorityQueue(){
        elem=new int[11];
        usedSize =0;
    }

    public void createHeap(int[] array){
        if (elem.length< array.length){
            elem=new int[array.length+2];
        }
        usedSize = array.length;

//        System.arraycopy(array, 0, elem, 0, usedsize);
        elem=Arrays.copyOf(array, usedSize);

        int ans=(usedSize -2)/2;

        while(ans>=0){
            shiftDown(ans, usedSize);
            ans--;
        }

    }


    private void shiftDown(int root ,int len){
        int ans=root;
        int child=ans*2+1;

        while(child<len){
            if (child+1<len&&elem[child]>elem[child+1]){
                ++child;
            }
            if (elem[child]<elem[ans]){
                swap(child,ans);
                ans=child;
                child=ans*2+1;
            }else {
                break;
            }

        }

    }

    private void swap(int pos1,int pos2){
        int temp=elem[pos1];
        elem[pos1]=elem[pos2];
        elem[pos2]=temp;
    }

    private void shiftUp(int child){
        int ans=(child-1)/2;

        while(child>0){
            if (elem[child]<elem[ans]){
                swap(child,ans);
                child=ans;
                ans=(child-1)/2;
            }else {
                break;
            }
        }

    }


    public void push(int val){
        if (isFull()){
            elem=new int[usedSize*2];
        }
        elem[usedSize]=val;
        shiftUp(usedSize);
        usedSize++;
    }



    public void pollHeap(){
        swap(0, usedSize -1);
        usedSize--;
        shiftDown(0, usedSize);
    }


    public boolean isFull(){
        return usedSize == elem.length;
    }

    public boolean isEmpty(){
        return usedSize ==0;
    }

    public int peekHeap(){
        return elem[0];
    }

//    public void print(){
//        for (int i = 0; i < usedsize; i++) {
//            System.out.println(elem[i]+" ");
//        }
//    }

}





class Solution {
    public int[] smallestK(int[] arr, int k) {
        if (arr.length==0||k==0){
            return new int[0];
        }

        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(Comparator.reverseOrder());

//        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2-o1;
//            }
//        });

        for (int i=0;i<k;i++){
            priorityQueue.add(arr[i]);
        }

        for (int i=k;i< arr.length;i++){
            int comp= priorityQueue.peek();
            if (arr[i]<comp){
                priorityQueue.poll();
                priorityQueue.add(arr[i]);
            }
        }

        int[] num=new int[k];
        for (int i=0;i<k;i++){
            num[i]=priorityQueue.poll();
        }

        return num;
    }
}









public class Main {
    public static void main(String[] args) {
        int[] arr={45,31,87,66,78,54};

        MyPriorityQueue priorityQueue=new MyPriorityQueue();

        priorityQueue.createHeap(arr);

        while(!priorityQueue.isEmpty()){
            System.out.print(priorityQueue.peekHeap()+" ");
            priorityQueue.pollHeap();
        }
        System.out.println();
        System.out.println("--------------------------");

        MyPriorityQueue priorityQueue1=new MyPriorityQueue();

        for (int j : arr) {
            priorityQueue1.push(j);
        }

        while(!priorityQueue1.isEmpty()){
            System.out.print(priorityQueue1.peekHeap()+" ");
            priorityQueue1.pollHeap();
        }
        System.out.println();

        System.out.println("--------------------------");

        Solution solution=new Solution();
        int[] arry=solution.smallestK(arr,3);

        for (int j:arry){
            System.out.print(j+" ");
        }
        System.out.println();

    }
}